import pandas as pd
import numpy as np


def load_data(file_path):
    data = pd.read_csv(file_path, header=None)
    return data


def entropy(y):
    value_counts = np.bincount(y)
    probabilities = value_counts / len(y)
    return -np.sum(probabilities * np.log2(probabilities + 1e-9))  


def best_attribute(X, y):
    base_entropy = entropy(y)
    best_gain = 0
    best_attr = -1
    n_samples, n_features = X.shape

    for i in range(n_features):
       
        values, counts = np.unique(X[:, i], return_counts=True)
        weighted_entropy = 0

        for v, count in zip(values, counts):
            subset_y = y[X[:, i] == v]
            weighted_entropy += (count / n_samples) * entropy(subset_y)

        gain = base_entropy - weighted_entropy
        if gain > best_gain:
            best_gain = gain
            best_attr = i

    return best_attr


def build_tree(X, y, depth=0, max_depth=None):
 
    if len(np.unique(y)) == 1:
        return np.unique(y)[0]

    
    if X.shape[1] == 0 or (max_depth is not None and depth >= max_depth):
        return np.argmax(np.bincount(y))

  
    best_attr = best_attribute(X, y)
    tree = {best_attr: {}}

    
    unique_values = np.unique(X[:, best_attr])

    for value in unique_values:
        subset_indices = (X[:, best_attr] == value)
        subset_X = X[subset_indices]
        subset_y = y[subset_indices]

       
        subtree = build_tree(np.delete(subset_X, best_attr, axis=1), subset_y, depth + 1, max_depth)
        tree[best_attr][value] = subtree

    return tree


def predict(tree, x):
    while isinstance(tree, dict):
        attribute = next(iter(tree))  
        attribute_value = x[attribute]
        if attribute_value in tree[attribute]:
            tree = tree[attribute][attribute_value]
        else:
            return None  
    return tree


if __name__ == '__main__':
    
    wine_data = load_data('wine.csv')

    
    X = wine_data.iloc[:, 1:].values  
    y = wine_data.iloc[:, 0].values    

  
    tree = build_tree(X, y)

    
    sample = X[0]  
    prediction = predict(tree, sample)
    print("预测结果：", prediction)